1. Field of the Invention
The present invention relates to a method of winner determination in combinatorial auctions.
2. Description of the Prior Art
Combinatorial auctions have emerged as a useful tool for determining resource allocations. Unfortunately, winner determination for combinatorial auctions is NP-hard and current methods have difficulty with combinatorial auctions involving goods and bids beyond the hundreds.
Combinatorial auctions are a form of auction in which a seller with multiple items for sale accepts bids on bundles, or combinations of items. When items exhibit complementarities for potential buyers, that is when certain items are less valuable unless complementary items are obtained, allowing combinatorial bids generally reduces a bidder's risk and allows for a more efficient allocation of goods, and greater seller revenue than had the items been auctioned individually, either sequentially or simultaneously. Given a set of combinatorial bids on a collection of items, the winner determination problem is that of allocating items to bidders, i.e., determining the winning bids/bundles, so as to maximize the seller's revenue. Applications of combinatorial auctions range from commodities trading, to resource allocation, to scheduling, to logistics planning, and the selling of any goods that exhibit complementarities, e.g., broadcast spectrum rights, airport gate allocations, and the like.
A combinatorial auction process will now be generally described with reference to FIG. 1. Assume a seller or auctioneer has a set G of M goods for sale and various potential buyers are interested in certain collections, or bundles, of these goods. Because of complementarities, the seller allows buyers to offer bundle bids. Namely, a buyer can offer to purchase a bundle of goods without committing to purchase anything but the complete bundle. A buyer can also bid on many distinct bundles involving overlapping bundles. Each bid B can comprise the entire set G or a subset of set G of the M goods and a corresponding monetary bid V. In a combinatorial auction, the seller can receive a collection of these bids from any number of potential buyers.
The problem of winner determination in a combinatorial auction is to find a subset of received bids where the sum of the monetary bid values of the non overlapping bids is maximal, thus maximizing the seller's revenue. Stated differently, the winner determination problem is to find an allocation where each bid is disjoint, and the sum of the monetary bids of the allocation is maximal.
It is an object of the present invention to provide a stochastic local search method that finds high quality, even optimal, allocations in a combinatorial auction much faster than prior art methods, particularly for large problems. Still other objects of the present invention will become apparent to those of ordinary skill in the art upon reading and understanding the following detailed description.